package com.gxc.graph;

import java.util.*;

/**
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 *
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 *
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 */
public class CanFinish {

    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; ++i) {
            edges.add(new ArrayList<Integer>());
        }
        visited = new int[numCourses];
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
        }
        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return valid;
    }

    public void dfs(int n) {
        visited[n] = 1;
        for (Integer i : edges.get(n)) {
            if (visited[i] == 1) {
                valid = false;
                return;
            } else if (visited[i] == 0){
                dfs(i);
                if (!valid) return;
            }
        }
        visited[n] = 2;
    }

    // 使用 BFS (Kahn 算法) 实现拓扑排序并返回排序结果
    public List<Integer> canFinishBFS(int numCourses, int[][] prerequisites) {
        // 1. 构建邻接表和入度数组
        List<List<Integer>> adjList = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }
        int[] inDegree = new int[numCourses];

        // 填充邻接表和入度数组
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int pre = prerequisite[1];
            adjList.get(pre).add(course);
            inDegree[course]++;
        }

        // 2. 将所有入度为0的节点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 3. 进行拓扑排序
        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int course = queue.poll();
            topoOrder.add(course);

            // 减少相邻节点的入度
            for (int nextCourse : adjList.get(course)) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }

        // 4. 判断是否所有节点都被处理
        if (topoOrder.size() == numCourses) {
            return topoOrder; // 返回拓扑排序结果
        } else {
            return new ArrayList<>(); // 存在环，返回空列表
        }
    }

    // 使用 DFS 检测环并生成拓扑排序
    public List<Integer> canFinishDFS(int numCourses, int[][] prerequisites) {
        // 1. 构建邻接表
        List<List<Integer>> adjList = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int pre = prerequisite[1];
            adjList.get(pre).add(course);
        }

        // 2. 状态数组：0=未访问，1=正在访问，2=已访问完毕
        int[] visited = new int[numCourses];
        // 存储拓扑排序结果（逆序）
        List<Integer> topoOrder = new ArrayList<>();

        // 3. 对每个节点进行DFS检测
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(i, adjList, visited, topoOrder)) {
                    return new ArrayList<>(); // 存在环，返回空列表
                }
            }
        }

        // 反转拓扑排序结果，得到正确顺序
        java.util.Collections.reverse(topoOrder);
        return topoOrder;
    }

    private boolean dfs(int course, List<List<Integer>> adjList, int[] visited, List<Integer> topoOrder) {
        // 如果正在访问，说明发现环
        if (visited[course] == 1) {
            return false;
        }
        // 如果已访问完毕，直接返回
        if (visited[course] == 2) {
            return true;
        }

        // 标记为正在访问
        visited[course] = 1;

        // 递归访问所有相邻节点
        for (int nextCourse : adjList.get(course)) {
            if (!dfs(nextCourse, adjList, visited, topoOrder)) {
                return false;
            }
        }

        // 标记为已访问完毕
        visited[course] = 2;
        // 将节点加入拓扑排序结果（逆序）
        topoOrder.add(course);
        return true;
    }

}
